// 9.3 顺序容器操作
/**
 * 顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。
 *
 * 9.3.6 容器操作可能使迭代器失效
 * 向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。
 * 在向容器添加元素后：
 * 1. 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。
 *    如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
 * 2. 对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。
 *    如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
 * 3. 对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
 * 当我们删除一个元素后：
 * 1. 对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
 * 2. 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。
 *    如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
 * 3. 对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。
 * 建议：由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。
 * 这个建议对vector、string和deque尤为重要。
 */

#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::cin, std::cout, std::endl;

int main()
{
    // 编写改变容器的循环程序
    // 程序必须保证每个循环步中都更新迭代器、引用或指针。
    // 如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter = vi.begin();
    while (iter != vi.end()) // 傻瓜循环，删除偶数元素，复制每个奇数元素
    {
        if (*iter % 2) // 如果是奇数
        {
            iter = vi.insert(iter, *iter); // 复制当前元素
            iter += 2;                     // 向前移动迭代器，跳过当前元素和已复制的元素
        }
        else                       // 如果是偶数
            iter = vi.erase(iter); // 删除偶数元素
                                   // 此时iter指向我们删除的元素之后的元素
                                   // 在调用erase后，不必递增迭代器，因为erase返回的迭代器已经指向序列中下一个元素。
    }

    // 不要保存end返回的迭代器
    // 当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效
    // 添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。
    // 通常C++标准库的实现中end（）操作都很快，部分就是因为这个原因。
    // 例如，考虑这样一个循环，它处理容器中的每个元素，在其后添加一个新元素。我们希望循环能跳过新添加的元素，只处理原有元素。
    // 在每步循环之后，我们将定位迭代器，使其指向下一个原有元素。
    // 如果我们试图“优化”这个循环，在循环之前保存end（）返回的迭代器，一直用作容器末尾，就会导致一场灾难：
    vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto begin = v.begin(),
         end = v.end();  // 保存尾后迭代器的值是一个坏主意
    while (begin != end) // 灾难：此循环的行为是未定义的
    {
        ++begin;                     // 向前移动begin，因为我们想在此元素之后插入一个元素
        begin = v.insert(begin, 42); // 插入新值
        ++begin;                     // 向前移动begin跳过我们刚刚加入的元素
    }
    // 必须在每次插入操作后重新调用end（），而不能在循环开始前保存它返回的迭代器：
    while (begin != v.end())
    {
        ++begin;                     // 向前移动begin，因为我们想在此元素之后插入一个元素
        begin = v.insert(begin, 42); // 插入新值
        ++begin;                     // 向前移动begin跳过我们刚刚加入的元素
    }

    return 0;
}